perm filename MIDTRM.XGP[206,LSP] blob sn#244785 filedate 1976-11-02 generic text, type T, neo UTF8
/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BDR30/FONT#2=BAXM30/FONT#3=BASB30/FONT#4=BDR30



␈↓ ↓H␈↓␈↓∧                                206 MIDTERM SOLUTIONS␈↓




␈↓ ↓H␈↓1. (a)  ␈↓αelement1[u,n] ← ␈↓β if n ␈↓αu ␈↓βthen ␈↓∧ERROR ␈↓βelse if␈↓αeq[n,1] ␈↓β then a ␈↓αu ␈↓βelse ␈↓αelement1[␈↓βd ␈↓αu,n-1]␈↓

␈↓ ↓H␈↓   (b)  ␈↓αelement2[x,s] ←
␈↓ ↓H␈↓α␈↓βif n ␈↓αs ␈↓βthen ␈↓αx ␈↓β else if ␈↓αat[x] ␈↓βthen ␈↓∧ERROR ␈↓βelse ␈↓αelement2[␈↓βif eq␈↓α[␈↓βa ␈↓αs,␈↓∧A␈↓α] ␈↓βthen a ␈↓αx ␈↓βelse d ␈↓αx,␈↓βd ␈↓αs]␈↓

␈↓ ↓H␈↓2. (a)  ␈↓αselectatoms1[u] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧NIL ␈↓βelse if at a␈↓α[u] ␈↓βthen a␈↓α[u].selectatoms1[␈↓βd ␈↓αu]
␈↓ ↓H␈↓α␈↓βelse ␈↓αselectatoms1[␈↓βd ␈↓αu]␈↓

␈↓ ↓H␈↓   (b)  ␈↓αselectatoms2[x] ← selat2[x,␈↓∧NIL␈↓α]
␈↓ ↓H␈↓αselat2[x,v] ← ␈↓βif at ␈↓αx ␈↓βthen if ␈↓αmember[x,v] ␈↓βthen ␈↓αv ␈↓βelse ␈↓αx.v ␈↓βelse ␈↓αselat2[␈↓βa ␈↓αx,selat2[␈↓βd ␈↓αx,v]]␈↓

␈↓ ↓H␈↓   (c)  ␈↓αselect1[p,u] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧NIL ␈↓βelse if ␈↓αp ␈↓βa ␈↓αu ␈↓βthen a␈↓α[u].select1[p,␈↓βd ␈↓αu] ␈↓βelse ␈↓αselect1[p,␈↓βd ␈↓αu]␈↓

␈↓ ↓H␈↓   (d)  ␈↓αselect2[p,x] ←
␈↓ ↓H␈↓α{␈↓βif ␈↓αp x ␈↓βthen list ␈↓αx ␈↓βelse ␈↓∧NIL␈↓α}[λ w.␈↓βif at ␈↓αx ␈↓βthen ␈↓αw ␈↓βelse ␈↓αw * [select2[p,␈↓βa ␈↓αx] * select2[p,␈↓βd ␈↓αx]]]␈↓

␈↓ ↓H␈↓   (e)  ␈↓αselect3[p,x] ← sel3[p,x,␈↓∧NIL␈↓α]
␈↓ ↓H␈↓αsel3[p,x,s] ←    {␈↓βif ␈↓αp x ␈↓βthen list ␈↓αreverse[s] ␈↓βelse ␈↓∧NIL␈↓α}
␈↓ ↓H␈↓α[λ w.␈↓βif at ␈↓αx ␈↓βthen ␈↓αw ␈↓βelse ␈↓αw * [select2[p,␈↓βa ␈↓αx,␈↓∧A.␈↓αs] * select2[p,␈↓βd ␈↓αx,␈↓∧D␈↓α.s]]]␈↓

␈↓ ↓H␈↓3. (a)  ␈↓αfind[x,p] ← f[␈↓βlist ␈↓αx,p,␈↓∧NIL␈↓α]
␈↓ ↓H␈↓αf[u,p,seen] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧NIL ␈↓βelse if ␈↓αp ␈↓βa ␈↓αu ␈↓βthen a ␈↓αu ␈↓βelse ␈↓α{f[␈↓βd ␈↓αu,p,␈↓βa ␈↓αu.seen]}
␈↓ ↓H␈↓α[λw.␈↓βif ␈↓αw ␈↓βthen ␈↓αw ␈↓βelse ␈↓αf[dif[successors[␈↓βa ␈↓αu],seen],p,␈↓βa␈↓α[u].seen]]

␈↓ ↓H␈↓α   (b)  findall[x,p] ← fa[␈↓βlist ␈↓αx,p,␈↓∧NIL]
␈↓ ↓H␈↓∧␈↓αfa[u,p,seen] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αunion[if p ␈↓βa ␈↓αu ␈↓βthen list␈↓α[␈↓βa ␈↓αu] ␈↓βelse ␈↓∧NIL␈↓α],
␈↓ ↓H␈↓αunion[fa[␈↓βd ␈↓αu,p,␈↓βa ␈↓αu.seen],fa[dif[successors[␈↓βa ␈↓αu],seen],p,␈↓βa␈↓α[u].seen]]]␈↓

␈↓ ↓H␈↓4. ␈↓αok[π] ← ok2[π,␈↓∧NIL,NIL␈↓α]
␈↓ ↓H␈↓αok2[π,ld,lu] ← ␈↓βif n ␈↓απ ␈↓βthen [if ␈↓αdif[lu,ld] then ␈↓∧NIL␈↓β else ␈↓∧T␈↓β] else
␈↓ ↓H␈↓βif at␈↓α[␈↓βa ␈↓απ] ␈↓βthen [if ␈↓αmember[a π,ld] ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αok2[␈↓βd ␈↓απ,␈↓βa␈↓α[π].ld,lu]] ␈↓βelse
␈↓ ↓H␈↓βif eq[a a ␈↓απ,␈↓∧GO␈↓β] then ␈↓αok2[␈↓βd ␈↓απ,ld,union[␈↓βd a ␈↓απ,lu]] ␈↓βelse
␈↓ ↓H␈↓βif eq[a a ␈↓απ,␈↓∧IF␈↓β] then ␈↓αok2[␈↓βd ␈↓απ,ld,union[␈↓βd d a ␈↓απ,lu]] ␈↓βelse
␈↓ ↓H␈↓β␈↓αok2[␈↓βd ␈↓απ,ld,lu]␈↓

␈↓ ↓H␈↓␈↓αdif ␈↓and ␈↓αunion ␈↓are given by:

␈↓ ↓H␈↓␈↓αdif[u,v] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧NIL ␈↓βelse if ␈↓αmember[␈↓βa ␈↓αu,v] ␈↓βthen ␈↓αdif[␈↓βd ␈↓αu,v] ␈↓βelse a␈↓α[u].dif[␈↓βd ␈↓αu,v]

␈↓ ↓H␈↓αunion[u,v] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αv ␈↓βelse if ␈↓αmember[␈↓βa ␈↓αu,v] ␈↓βthen ␈↓αunion[␈↓βd ␈↓αu,v] ␈↓βelse a␈↓α[u].union[␈↓βd ␈↓αu,v]